238. Product of Array Except Self
题目 238. Product of Array Except Self
思路分析
不能用除法 而且如果就算用除法 /0 的其他乘积和不好求
用前缀积 和 后缀积 （貌似不需要）
s[idx-1]是左边的积
s[n] / s[idx]是右边的积
相乘 就是去除当前位的积
所以这里发现不行 用到了除法 且有0问题
- 前缀 和（Sum）：求右半部分和 =
TotalSum - PreSum。这是减法。 - 前缀积 5（Product）：求右半部分积 =
TotalProduct / PreProduct。这是除法。
左右乘积法
对于任意索引 i，除了它自己以外的乘积 = (i 左边的所有数的积)\(\times\)(i 右边的所有数的积)。
我们可以显式地创建两个数组：
L数组：L[i]存i左边所有数的乘积。R数组：R[i]存i右边所有数的乘积。
假设输入 nums = [1, 2, 3, 4]
| i | nums[i] | L 数组 (左侧积) | R 数组 (右侧积) | 结果 (L[i] * R[i]) |
|---|---|---|---|---|
| 0 | 1 | 1 (无元素，补1) | \(2\times3\times4=\) 24 | \(1 \times 24 = 24\) |
| 1 | 2 | \(1=\) 1 | \(3\times4=\) 12 | \(1 \times 12 = 12\) |
| 2 | 3 | \(1\times2=\) 2 | \(4=\) 4 | \(2 \times 4 = 8\) |
| 3 | 4 | \(1\times2\times3=\) 6 | 1 (无元素，补1) | \(6 \times 1 = 6\) |
代码实现
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] L = new int[n];
int[] R = new int[n];
// 2. 填充前缀积数组 L
// L[i] 表示 i 左侧所有元素的乘积
L[0] = 1; // 索引0左边没有数，初始化为1
for (int i = 1; i < n; i++) {
// L[i] = (i-1左边的积) * (i-1本身的值)
L[i] = L[i - 1] * nums[i - 1];
}
// 3. 填充后缀积数组 R
// R[i] 表示 i 右侧所有元素的乘积
R[n - 1] = 1; // 索引n-1右边没有数，初始化为1
for (int i = n - 2; i >= 0; i--) {
// R[i] = (i+1右边的积) * (i+1本身的值)
R[i] = R[i + 1] * nums[i + 1];
}
// 4. 计算最终结果
int[] answer = new int[n];
for (int i = 0; i < n; i++) {
answer[i] = L[i] * R[i];
}
return answer;
}
}
💬 评论